0% completed
Problem Statement
Given two strings str1 and str2, return the index of first occurrences of the str2 string in str1. If str2 doesn't exists in str1 string, return -1.
Examples
-
Example 1:
- Input:
str1 = "algorithms", str2 = "rith" - Expected Output:
4 - Justification: The substring
"rith"begins at index 4 in the string"algorithms".
- Input:
-
Example 2:
- Input:
str1 = "openai", str2 = "ai" - Expected Output:
4 - Justification: The substring
"ai"starts at index 4 in the string"openai".
- Input:
-
Example 3:
- Input:
str1 = "challenge", str2 = "test" - Expected Output:
-1 - Justification: The substring
"test"does not appear in the string"challenge", hence the output is -1.
- Input:
Solution
To solve this problem, we'll adopt a straightforward search approach. We iterate through the main string (str1) and for each position, we check if the following characters match the target substring (str2).
This method is effective because it directly compares segments of the str1 with the str2, ensuring that no possible starting point is overlooked. The key to this approach's effectiveness lies in its meticulous examination of each potential match point, guaranteeing that as soon as the str2 is found, its starting index is immediately returned, optimizing for both clarity and efficiency.
Step-by-step Algorithm
- Start by checking if the str2 is empty. If it is, return 0, as an empty string is considered to be found at the beginning.
- Loop through the str1 string starting from index 0.
- For each index in the str1, compare the substring that starts at this index and spans the length of the str2 with the str2 itself.
- If a match is found, return the current index as the starting point of the str2 in the str1.
- If no match is found by the end of the loop, return -1 to indicate the str2 was not found in the str1.
Algorithm Walkthrough
Using the input str1 = "algorithms", str2 = "rith":
-
Initialization: We start with
str1 = "algorithms"andstr2 = "rith". The goal is to find the first occurrence ofstr2instr1. -
Check for Empty
str2: First, check ifstr2is empty. Sincestr2is not empty, we proceed to the next step. -
Start Looping Through
str1:- We initiate a loop that starts from index 0 of
str1and will go up tostr1.length - str2.lengthto ensure we can compare the full length ofstr2without going out of bounds.
- We initiate a loop that starts from index 0 of
-
Index 0 (
i = 0):- Compare
str1.substring(0, 4)("algo") withstr2("rith"). - The substring does not match
str2. Move to the next index.
- Compare
-
Index 1 (
i = 1):- Compare
str1.substring(1, 5)("lgor") withstr2. - The substring does not match
str2. Move to the next index.
- Compare
-
Continue Looping Until Index 4:
- At each index, we are slicing
str1from the current indexitoi + str2.lengthand comparing it withstr2.
- At each index, we are slicing
-
Index 4 (
i = 4):- At index 4, the substring of
str1isstr1.substring(4, 8)("rith"). - This substring matches
str2exactly.
- At index 4, the substring of
-
Match Found:
- Since the substring starting from index 4 matches
str2, we return 4 as the index wherestr2first occurs instr1.
- Since the substring starting from index 4 matches
Code
Complexity Analysis
`
- Time Complexity:
, where nis the length of the str1 andmis the length of the str2. In the worst case, we need to check each substring of the str1 that has the same length as the str2. - Space Complexity:
, as we only use a few variables for iteration and comparison, regardless of the input size.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis